#! /usr/bin/env python3
# coding=utf-8



"""
   left part             right part
A[0]... A[i - 1]   |  A[i]... A[m - 1]
B[0]... B[j - 1]   |  B[j]... B[n - 1]

try to find i and j that meet the condition:
1. len(left part) = len(right part)
2. A[i] > B[j - 1] && B[j] > A[i - 1]

for the 1th condition:
i and j should meet following condition:
i + j = m + n + i + j (if (m + n) is even)
or i + j == m + n + i + j + 1 (if (m + n) is odd)
"""

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        if len(nums1) == 0 and len(nums2) == 0:
            return None

        if len(nums1) > len(nums2):
            A, B, m, n = nums2, nums1, len(nums2), len(nums1)
        else:
            A, B, m, n = nums1, nums2, len(nums1), len(nums2)

        low = 0
        high = m
        while low <= high:
            mid = (low + high)//2
            i = mid
            j = (m + n + 1)//2 - i
            if i < m and A[i] < B[j - 1]:
                low = i + 1
            elif i > 0 and A[i - 1] > B[j]:
                high = i - 1
            else:
                if i == 0:
                    left_max = B[j - 1]
                elif j == 0:
                    left_max = A[i - 1]
                else:
                    left_max = max(A[i - 1], B[j - 1])

                if (m + n) % 2 == 1:
                    return left_max

                if i == m:
                    right_min = B[j]
                elif j == n:
                    right_min = A[i]
                else:
                    right_min = min(A[i], B[j])
                return (right_min + left_max) / 2

s = Solution()
s.findMedianSortedArrays(
    [1, 2],
    [3, 4]
)